package leetcode.code077.Combinations;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ???
 * @date 2021年8月22日
 * @description
 */
public class Solution7702WrongUnFinished extends Combinations {

	@Override
	public List<List<Integer>> combine(int n, int k) {
		Map<String, List<List<Integer>>> cache = new HashMap<>();
		return this.f(n, k, 1, 1, cache);
	}

	/**
	 * cache不好用
	 *
	 * @param n
	 * @param k
	 * @param no
	 * @param min
	 * @param cache
	 * @return
	 */
	private List<List<Integer>> f(int n, int k, int no, int min, Map<String, List<List<Integer>>> cache) {
		System.out.println("f(" + no + "," + min + ")");
		if (no > k)
			return null;
		String key = no + "" + min;
		List<List<Integer>> result = new ArrayList<>();
		for (int i = min; i <= n - k + no; i++) {
			int num = i;
			List<List<Integer>> sublist = f(n, k, no + 1, num + 1, cache);
			if (sublist != null && sublist.size() != 0) {
				for (List<Integer> sub : sublist) {
					sub.add(num);
					result.add(sub);
				}
			} else {
				List<Integer> list = new ArrayList<>();
				list.add(i);
				result.add(list);
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution7702WrongUnFinished so = new Solution7702WrongUnFinished();
//		so.debug1();
		so.debug2();
//		so.debug3();
//		so.debug4();
	}

}
